package com.njupt.LinkTable;

import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/7/11 23:30
 * @Description: 148. 排序链表
 * @Version: 1.0
 */


public class SortList_148 {

    public ListNode sortList1(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode p = head;

        ListNode head1 = new ListNode();
        head1.next = new ListNode(p.val);
        p = p.next;

        ListNode pre = head1;
        ListNode rear = head1.next;

        while (p != null) {
            //确定节点p的位置
            while (rear != null && p.val > rear.val) {

                rear = rear.next;
                pre = pre.next;


            }
            ListNode temp = new ListNode(p.val);
            temp.next = rear;
            pre.next = temp;
            pre = head1;
            rear = head1.next;


            p = p.next;
        }
        return head1.next;
    }


    public ListNode sortList(ListNode head){
        return sortList(head,null);
    }

    public ListNode sortList(ListNode head,ListNode tail){
        if(head == null){
            return head;
        }

        if(head.next == tail){
            head.next = null;
            return head;
        }

        ListNode fast = head,slow = head;
        while(fast != tail){
            slow = slow.next;
            fast = fast.next;
            if(fast != tail){
                fast = fast.next;
            }
        }

        ListNode mid = slow;
        ListNode head1 = sortList(head, mid);
        ListNode head2 = sortList(mid, fast);
        ListNode sorted = merge(head1,head2);
        return sorted;
    }

    private ListNode merge(ListNode head1, ListNode head2) {

        ListNode head = new ListNode(0);

        ListNode temp = head;
        ListNode temp1 = head1; ListNode temp2 = head2;
        while (temp1 != null && temp2 != null){
            if(temp1.val < temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        while(temp1 != null){
            temp.next = temp1;
            temp1 = temp1.next;
        }

        while(temp2 != null){
            temp.next = temp2;
            temp2 = temp2.next;
        }

//        if (temp1 != null) {
//            temp.next = temp1;
//        } else if (temp2 != null) {
//            temp.next = temp2;
//        }
        return head.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(1);
//        ListNode node3 = new ListNode(4);
//        ListNode node4 = new ListNode(0);
        head.next = node1;
        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;

        SortList_148 test = new SortList_148();
        ListNode listNode = test.sortList(head);

        ListNode p = listNode;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }

    }
}
